#include <chrono>
#include <iostream>
// # include <sstream>
// # include <windows.h>

using namespace std;

struct link {
  int data;
  link *next;
};

link *initLink(int nodeNum) {
  link *head = new link{};
  link *temNode = head;

  // 正式创建含有值的链表元素
  for (int i = 1; i <= nodeNum; i++) {
    link *item = new link(i, nullptr);
    temNode->next = item;
    temNode = item;
  }

  return head;
}

// 根据指定数据查找目标节点
void searchLinkData(link *head, int destData) {
  link *cursorLinkNode = head->next;
  int i = 0;

  while (cursorLinkNode) {
    i++;
    if (cursorLinkNode->data == destData) {
      cout << "第 " << i << " 次，寻找到了目标值：" << destData << endl;
    }
    cursorLinkNode = cursorLinkNode->next;
  }
}

int main() {
  std::cout << std::fixed;
  auto start = std::chrono::high_resolution_clock::now();
  int nodeNum = 500000; // 50万节点的单链表
  link *head = initLink(nodeNum);
  for (int i = 0; i < 10; i++) {
    searchLinkData(head, nodeNum);
  }
  // 获取结束时间点
  auto end = std::chrono::high_resolution_clock::now();
  // 计算运行时长
  std::chrono::duration<double> elapsed_seconds = end - start;
  cout << " 单次平均耗时(ms)：" << elapsed_seconds.count() * 1000 / 10 << endl;

  return 0;
}